This invention relates generally to the automated design of integrated circuits (ICs) and more particularly to the automated synthesis of state machines.
Several types of computer aided design (CAD) tools are used to design and fabricate integrated circuits. An important CAD tool for IC design is the "behavioral synthesis" design tool wherein the behavior (e.g. inputs, outputs, functionality, etc.) of a desired IC are entered into a computer system, and synthesis software running on the computer designs an integrated circuit that exhibits that behavior. Such tools permit integrated circuit designers to produce increasingly complex integrated circuits, sometimes numbering in the millions of gates, with fewer errors and in a much shorter time than would be possible with manual design techniques.
The process of behavioral synthesis begins with integrated circuit specifications encoded in a hardware description language (HDL) such as Verilog.RTM. available from Cadence Design Systems, Inc. of Santa Clara, Calif. or VHDL.RTM. available from IEEE of New York, N.Y. Specifications define an integrated circuit in terms of desired inputs and outputs, as well as desired functionality such as clock speed. From the HDL, a "netlist" including a list of gates and their interconnections is generated which describes the circuitry of the desired IC.
Automated IC design can include both synthesis and optimization. As is well known to those skilled in the art, synthesis includes any desired combination of synthesis techniques which occur as various levels of abstraction. In particular, architectural level synthesis, logic level synthesis, and geometrical level synthesis may be incorporated into IC design methods.
Architectural level synthesis operates with functional blocks, their interconnections and, to some extent, their internal operations. In other words, architectural level synthesis is concerned with the macroscopic structure of the circuit. Architectural level synthesis includes register transfer (RT) level synthesis, which can have multi-bit components such as registers and operators.
Logic level synthesis is concerned with gate level design. Logic level synthesis determines a microscopic structure of a circuit and transforms a logic model into an interconnection of instances of library cells. The result of the logic level synthesis is a netlist of logic devices and their interconnections. In the past, state machine synthesis was performed at the logic synthesis level and included optimization such as state minimization and state encoding. Logic-level synthesizers are available commercially from such companies as Synopsis, Inc. of Mountain View, Calif.
Geometrical level synthesis (sometimes called chip compilation) results in a physical layout of devices and their interconnections. The geometrical level synthesis is sometimes referred to as physical design and provides a link between circuit design and fabrication. The geometrical level layout (mask layout) represents all circuit geometries and is used to control an apparatus which fabricates I.C. masks. The layout is a set of two-dimensional layers corresponding to a number of masks. The relative position of the circuit geometries corresponds to the I.C. devices as well as to device interconnections. The fabrication masks are used in photolithographic equipment during the manufacture of integrated circuits having the desired functionality. Typical chip compilers and mask layout tools may be, for example, those which are commercially available from a number of vendors including Compass Design Automation of San Jose, Calif.
A process of prior art automated design is shown in FIG. 1a and includes state machine extraction at a logic level. In this prior art process, HDL descriptions are transformed into a logic level representation. A state machine transition table is extracted bit-by-bit from a Boolean equation at the logic level. In a n=16 bit structure, for example, the step of state machine extraction is repeated 16 times. This repetitive state machine extraction is computationally intensive and, therefore, slow and expensive. After the n state machine extractions are made, a state machine generator combines the n state machines and inputs the state machines into a chip compiler. The output of the chip compiler is used to create IC masks in a mask layout tool, and integrated circuits are produced using the IC masks.
The state machine representations derived from the logic level representations may be optimized by an appropriate technique, such as a state encoding or a logic minimization technique. These techniques optimize the state transition table (STT) or state transition graphs (STG) which represent state machines.
State transition tables are typically extracted from structural netlists at the logic level when a set of sequential elements used as state register are provided. Except for sequential components, all combinational logic is extracted. Extracting all combinational logic, however, is computationally burdensome and therefore undesirable.
In higher-level synthesis, (e.g. architectural level) state machine extraction from a STT derived from a previously scheduled data control flow graph has been attempted in conjunction with control unit synthesis. This technique is described by S. Hayati and A. Parker, in "Automatic Production Of Controller Specifications From Control And Timing Behavioral Descriptions", Proc. 26th Design autornation Conference, 1989; and by D. Grant, and P. Denyer, in "Memory, Control, and Communications Synthesis for Scheduled Algorithms", 27th Design Automation Conference, 1990. However, high-level synthesis including extraction of state machines from behavioral HDL's has not been addressed.